#include <iostream>
#include <stack>
#include "RBTree.h"
using namespace std;
 RBTree::node_ptr RBTree::nulptr = nullptr;
bool RBTree::RED = false;
bool RBTree::BLACK = true;
void RBTree::left_rotate(node_ptr x)
{
	if(x != nullptr){
		node_ptr r = x->right;
		//首先将子节点的左结点转移到当前结点的右子上
		x->right = r->left;
		if(r->left != nullptr)
			r->left->parent = x;
		r->parent = x->parent;
		if(x->parent == nullptr){
			root = r;
		}else if (x->parent->left == x){
			x->parent->left = r;
		}else{
			x->parent->right = r;
		}
		r->left = x;
		x->parent = r;
	}
}

void RBTree::right_rotate(node_ptr x)
{
	if(x != nullptr){
		node_ptr r = x->left;
		//首先将子节点的左结点转移到当前结点的右子上
		x->left = r->right;
		if(r->right != nullptr)
			r->right->parent = x;
		r->parent = x->parent;
		if(x->parent == nullptr){
			root = r;
		}else if (x->parent->left == x){
			x->parent->left = r;
		}else{
			x->parent->right = r;
		}
		r->right = x;
		x->parent = r;
	}
}
RBTree::node_ptr RBTree::RBInsert(int key)
{
	node_ptr t = root;
	node_ptr par = nullptr;
	if(t == nullptr){
		root = new RBNode(key);
		_size++;
		return root;
	}
	while(t != nullptr)
	{
		par = t;
		if(t->key > key)
			t = t->left;
		else if(t->key <  key)
			t = t->right;
		else
			return nullptr;	
	}	
	//找到待插入位置了
	t = new RBNode(key);
	if(par->key > key)
		par->left = t; 
	else 
		par->right = t; 
	t->parent = par;		
	//然后开始调正颜色
	_size++;
	RB_insert_fixup(t);
}

RBTree::node_ptr RBTree::parentof(node_ptr cur)
{
	return (cur == nullptr) ? nullptr : cur->parent;
}
RBTree::node_ptr RBTree::leftof(node_ptr cur)
{
	return (cur == nullptr) ? nullptr : cur->left;
}
RBTree::node_ptr RBTree::rightof(node_ptr cur)
{
	return (cur == nullptr) ? nullptr : cur->right;
}

void RBTree::setcolor(node_ptr cur,bool color)
{
	if(cur != nullptr)
		cur->color = color;
}
bool RBTree::getcolor(node_ptr cur) const
{
	return (cur == nullptr) ? BLACK : cur->color;
}
void RBTree::RB_insert_fixup(node_ptr z)
{
	z->color = RED;
	while(z != nullptr && z != root && z->parent->color == RED){
		//对应清空就是2,3
		if(parentof(z) == leftof(parentof(parentof(z))) ){
			node_ptr bro = rightof(parentof(parentof(z)));
			if(getcolor(bro) == RED)
			{
				setcolor(bro,BLACK);
				setcolor(parentof(z),BLACK);
				setcolor(parentof(parentof(z)),RED);	
				z = parentof(parentof(z));
			}else
			{
				if(z == rightof(parentof(z))){
					z = parentof(z);
					left_rotate(z);
				}
				setcolor(parentof(z),BLACK);
				setcolor(parentof(parentof(z) ),RED);	
			
				right_rotate(parentof(parentof(z)) );
			}
		}else{
			node_ptr bro = leftof(parentof(parentof(z)));
			if(getcolor(bro) == RED)
            {   
                setcolor(bro,BLACK);
                setcolor(parentof(z),BLACK);
                setcolor(parentof(parentof(z)),RED);
				z = parentof(parentof(z));
            }else
            {
				if(z == leftof(parentof(z))){
                    z = parentof(z);
                    right_rotate(z);
                }
				setcolor(parentof(z),BLACK);
                setcolor(parentof(parentof(z) ),RED);

                left_rotate(parentof(parentof(z)) );
			}
		}		
	}

	root->color = BLACK;
}

void RBTree::PrintTree()
{
	//用迭代实现中序遍历吧
	if(root == nullptr) return;
	stack<node_ptr> sk;
	node_ptr tmp = root;
	while(tmp || !sk.empty())
	{
		while(tmp){
			sk.push(tmp);
			tmp = tmp->left;
		}
		tmp = sk.top();
		sk.pop();
		cout << tmp->key << "\t";
		tmp = tmp->right;
	}	
	cout << endl <<"当前元素数量为:" <<  _size << endl;
	return ;
}
void RBTree::destroy(node_ptr val)
{}
